﻿package com.astar

{
	import flash.geom.Point; 

	/**
	 * 二叉堆Astar寻路	
	 * @author Jackmist
	 */
	public class AstarFinder
	{

		private var StartX: int = 0;//起始坐标
		private var StartY: int = 0;
		private var EndX: int = 1;//结束坐标
		private var EndY: int = 1;   
		private var G_R: int = 10;//直角移动代价
		private var G_D: int = 14;//斜角移动代价
		private var BanCorner: Boolean = true;//是否允许斜方向移动
		private var path: Array = [];//路径集合
		private var StartNode: String = "";
		private var EndNode: String = "";
		private var Node: Object = {}; 
		private var Open: Object = {};
		private var Close: Object = {};
		private var Heaps: Array = [];
		private var OpenLength: int = 0; 
		private var chkHinder: Boolean = true;
		private static var hinder: Object = {};//障碍点
		private static var mapWidth: int = 0;
		private static var mapHeight: int = 0;

		//开始寻找
		public function find(sx: int,sy: int,ex: int,ey: int): Array
		{
			this.StartX = sx;
			this.StartY = sy;
			this.EndX = ex;
			this.EndY = ey;
			//var st: int = getTimer(); 
			this.StartNode = this.StartX + "," + this.StartY;
			this.EndNode = this.EndX + "," + this.EndY;
			//如果起点就是终点,返回.
			if (this.StartNode == this.EndNode)
			{
				return [];
			}
		 
			 
			 
			//清空
			this.path = [];
			this.Node = {};
			this.Open = {};
			this.Close = {};
			this.Heaps = [];

			this.Node[this.StartNode] = [this.StartX,this.StartY];
			this.Node[this.StartNode].G = 0;// 移动代价0
			this.Open[this.StartNode] = true;//放入Open列表
			this.OpenLength = 1;//Open列表的个数
			this.Heaps.push([0,this.StartNode] );

			while (! this.Open[this.EndNode] && this.OpenLength)
			{
				this.GetNode(); 
			} 
			//搜索完毕
			if (this.Open[this.EndNode])
			{
				var par: Object = this.Node[this.EndNode].par;
				while (par != this.StartNode)
				{
					this.path.push(this.Node[par] );
					par = this.Node[par].par;
				} 
			} 
			else
			{ 
				return [];
			}
			this.path.reverse();
			this.path.push([this.EndX, this.EndY] ); 
			//trace("用时:" + (getTimer() - st) );
			return this.path;
		}

		//绑定一个2维数组格式的地图数据
		public function bindMapData(hinder: Object,mapWidth: uint,mapHeight: uint): void
		{
			AstarFinder.hinder = hinder;
			AstarFinder.mapWidth = mapWidth;
			AstarFinder.mapHeight = mapHeight;
		}

		//获取离某点最近的非障碍点
		public function getNearlyPt(sx: int,sy: int,ex: int,ey: int): Point
		{
			this.chkHinder = false;
			var tmp: Array = this.find(sx, sy, ex, ey );
			this.chkHinder = true;
			//如果是忽略障碍，则去除帐碍部分
			for(var i: int = tmp.length - 1;i > 0; i --)
			{
				if(! AstarFinder.hinder[tmp[i][0] + "," + tmp[i][1]])
				{
					return new Point(tmp[i][0], tmp[i][1] );
				}
			} 
			return null;
		}

		//获取节点
		private function GetNode(): void
		{
 
			var xy: String = this.MinF_Node();//删除并返回二堆叉中的第一个元素(最小值) 
			var x: int = this.Node[xy][0];//获取该元素的坐标 
			var y: int = this.Node[xy][1]; 
			delete this.Open[xy];//从开启列表里删除该点 
			this.OpenLength --;//开启列表长度减1 
			this.Close[xy] = true;//把该点添加到封闭列表
 
			//获取周围的八方向格子 
			this.Set_Node(x, y, x + 1, y );//右
			this.Set_Node(x, y, x - 1, y );//左
			this.Set_Node(x, y, x, y + 1 );//下
			this.Set_Node(x, y, x, y - 1 );//上
			this.Set_Node(x, y, x + 1, y + 1 );//右下
			this.Set_Node(x, y, x + 1, y - 1 );//右上
			this.Set_Node(x, y, x - 1, y - 1 );//左上
			this.Set_Node(x, y, x - 1, y + 1 );//左下 
		}

		private function Set_Node(parX: int, parY: int, x: int, y: int ): void
		{ 
			//是否超出边界
			if (x < 0 || y < 0 || x > AstarFinder.mapWidth || y > AstarFinder.mapHeight) 
			{
				return;
			} 
			//是否障碍拐角
			if (chkHinder && this.BanCorner && (AstarFinder.hinder[x + "," + parY] || AstarFinder.hinder[parX + "," + y]))
			{			
				return;
			} 
			var xy: String = x + "," + y;
			//是否障碍 
			if (chkHinder && AstarFinder.hinder[xy]) 
			{  
				return; 
			}  
			//是否在封闭列表
			if (this.Close[xy])
			{
				return;
			} 
			var par: String = parX + "," + parY;

			//当前移动代价,利用新格xy与他的父格的xy相减,如果是直角移动,必定有x或y不变,那么相乘后得到0,0即为false,用!号反意,即为true     
			var G: int = ! ((parX - x) * (parY - y)) ? this.G_R:this.G_D;
			//与父格的G值相加 
			var NowNodeG: int = this.Node[par].G + G;
			//在开放列表中
			var node: Object;
			if (this.Open[xy])
			{
				node = this.Node[xy];
				//如果当前点的G值比父格还小
				if (NowNodeG < node.G)
				{
					node.par = par;
					node.G = NowNodeG;
					node.F = node.G + node.H;
					//修改二叉堆
					this.Revise_Node(node.F, xy );
				}
			} 
			else
			{
				// 设置为新的当前点
				this.Node[xy] = [x,y];
				node = this.Node[xy]; 
				//估算距离值 
				var M: int = Math.abs((this.EndX - x) ) + Math.abs((this.EndY - y) );

				//设置新加节点的相关值 
				node.par = par;
				node.H = M * this.G_R;
				node.G = NowNodeG;
				node.F = node.G + node.H;
				this.Open[xy] = true;
				this.OpenLength ++; 
				this.Add_Node([node.F, xy] );
			}
		} 

		//二叉堆相关函数 
 
		//—堆数组下标互换返回a   
		private function Swap(a: int, b: int): int
		{
			var temp: Object = this.Heaps[a];
			this.Heaps[a] = this.Heaps[b];
			this.Heaps[b] = temp;
			return a;
		}

		//添加元素到堆 
		private function Add_Node(Arr: Array): void
		{
			this.Heaps.push(Arr );
			if (this.Heaps.length == 1)
			{
				return;
			} 
			var NodeIndex: int = this.Heaps.length - 1;
			var parIndex: int = Math.floor((NodeIndex + 1) / 2 ) - 1;

			while (this.Heaps[parIndex][0] > Arr[0])
			{
				NodeIndex = this.Swap(parIndex, NodeIndex );
				parIndex = Math.floor((NodeIndex + 1) / 2 ) - 1;
				if (parIndex < 0)
				{
					return;
				}
			}
		}

		//删除堆里第一个元素并返回  
		private function MinF_Node(): String
		{ 
			// 判断并得到子节点
			var Child1: Object,Child2: Object;
			if (this.Heaps.length > 3)
			{
				Child1 = this.Heaps[1][0];
				Child2 = this.Heaps[2][0];
			} 
			else if (this.Heaps.length < 3)
			{
				return this.Heaps.shift()[1];
			} 
			else
			{
				Child1 = this.Heaps[1][0];
				Child2 = "undefined";
			}
			var NodeIndex: int = this.Swap(0, this.Heaps.length - 1 );
			var MinNode: String = this.Heaps.pop()[1];
			var ChildIndex1: int = 1;
			var ChildIndex2: int = 2;

			while (this.Heaps[NodeIndex][0] > Child1 || this.Heaps[NodeIndex][0] > Child2)
			{
				// 返回比较小的字节点值的下标，并和节点互换，获得新的节点下标
				NodeIndex = this.Swap(Child2 < Child1 ? ChildIndex2:ChildIndex1, NodeIndex );
				ChildIndex1 = NodeIndex * 2 + 1;
				ChildIndex2 = NodeIndex * 2 + 2;

				// 判断子节点是否存在并附值
				if (ChildIndex1 >= this.Heaps.length - 1)
				{
					if (ChildIndex1 == this.Heaps.length - 1)
					{
						Child1 = this.Heaps[ChildIndex1][0];
						Child2 = "undefined";
					} 
					else
					{
						break;
					}
				} 
				else
				{
					Child1 = this.Heaps[ChildIndex1][0];
					Child2 = this.Heaps[ChildIndex2][0];
				}
			}
			return MinNode;
		}

		//修改堆里的元素 
		private function Revise_Node(F: Object,xy: Object): void
		{
			for (var i: int = 0;i < this.Heaps.length; i ++)
			{
				if (this.Heaps[i][1] == xy)
				{
					this.Heaps[i][0] = F;
					var parIndex: int = Math.floor((i + 1) / 2 ) - 1;
					if (i > 0 && this.Heaps[parIndex][0] > F)
					{
						this.Swap(parIndex, i );
						return;
					}
				}
			}
		} 
	} 
}